"""
在 Python 中，图（Graph）主要有两种常用的表示方式：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
题目：使用邻接表表示图，并实现图的基本创建功能。
"""


class Graph:
    def __init__(self, is_directed=False):
        #字典的键是图中的顶点（可以是任意可哈希的类型，比如整数、字符串等）。
        #字典的值通常是一个集合或列表，存储与该顶点直接相连的邻接顶点。
        self.vertices = {}  # 存储顶点与邻接顶点的映射
        self.is_directed = is_directed  # 是否为有向图
        #注意：这时候，还没有顶点！

    def add_vertex(self, vertex):
        """添加顶点"""
        if vertex not in self.vertices:
            self.vertices[vertex] = []  # 初始化邻接列表,初始化时，每一个顶点都是没有邻接的顶点的 等着后面的进一步操作；且每一个顶点的所有邻接点都是以集合的形式存储

    def add_edge(self, v1, v2):
        """添加边"""
        # 确保两个顶点都存在于图中(先有顶点，才会有边)
        self.add_vertex(v1)
        self.add_vertex(v2)
        # 向v1的邻接列表添加v2  注意：self.vertices[v1]的返回值是个集合，该集合表示的是v1的所有邻接顶点
        self.vertices[v1].append(v2)
        # 如果是无向图，需要添加反向边 即互相绑定一下
        if not self.is_directed:
            self.vertices[v2].append(v1)
        #如果不是无向图，则不互相添加
        #至此，v1,v2顶点有了，其构成的边也有了

    def get_vertices(self):
        """返回所有顶点"""
        return list(self.vertices.keys())

    def get_edges(self):
        """返回所有边"""
        edges = []
        #遍历该图的所有顶点
        for v1 in self.vertices:
            #针对每一个上面被遍历到的顶点,继续遍历它的所有邻接顶点
            for v2 in self.vertices[v1]:
                # 避免无向图中重复记录边
                #包含2种情况 1)如果是有向图，edges直接精确地添加  2)如果是无向图，要在避免重复添加的情况下添加
                if self.is_directed or ((v1, v2) not in edges and (v2, v1) not in edges):
                    edges.append((v1, v2)) #(v1, v2) 是一个元组
        return edges


# 测试
# 创建无向图
undirected_graph = Graph()
undirected_graph.add_edge('A', 'B')
undirected_graph.add_edge('A', 'C')
undirected_graph.add_edge('B', 'C')
print("无向图顶点:", undirected_graph.get_vertices())  # 输出: ['A', 'B', 'C']
print("无向图边:", undirected_graph.get_edges())  # 输出: [('A', 'B'), ('A', 'C'), ('B', 'C')]

# 创建有向图
directed_graph = Graph(is_directed=True)
directed_graph.add_edge('A', 'B')
directed_graph.add_edge('B', 'C')
directed_graph.add_edge('C', 'A')
print("有向图顶点:", directed_graph.get_vertices())  # 输出: ['A', 'B', 'C']
print("有向图边:", directed_graph.get_edges())  # 输出: [('A', 'B'), ('B', 'C'), ('C', 'A')]

print("-------------------------其他基础语法测试-----------------------------------")
dict1 = {"name": "Alice", "age": 25}
dict2 = {"city": "New York", "job": "Engineer"}
# 使用字典解包合并两个字典 这里通过 {**dict1, **dict2} 将 dict1 和 dict2 的键值对合并到一个新的字典 merged_dict 中，
# 如果两个字典有相同的键，后面字典中的值会覆盖前面字典中的值。
merged_dict = {**dict1, **dict2}
print(merged_dict)
print("-------------")
# 创建一个字典
my_dict = {"name": "Alice", "age": 25}
# 使用setdefault方法添加新键值对
result = my_dict.setdefault("city", "New York")
print(result)
print(my_dict)
print("-------------")
# 如果键已存在，setdefault不会修改其值，而是返回该键对应的值
existing_result = my_dict.setdefault("age", 30)
print(existing_result)
print(my_dict)

